package Experiment3;

import java.io.IOException;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.IndexMultiwayMinPQ;

/**
 * <p>
 * 解决许多最短路径问题，只打印最短距离而不打印路径
 * 
 * <p>
 * 由于只需要距离，可对对应Dijkstra算法做优化,去除存储最短路径的部分以降低空间开销与时间开销
 * 
 * @author Chen Junjie
 */
public class Distances {
    private MyDijkstraForDistances m;

    public Distances(EuclidienGraph graph, String request_data) {
        m = new MyDijkstraForDistances(graph);
        Scanner sc = null;
        try {
            Path path = java.nio.file.Paths.get(".\\src\\Experiment3\\" + request_data);
            sc = new Scanner(path.toFile());

            while (sc.hasNextInt()) {
                int source = sc.nextInt();
                int destination = sc.nextInt();
                m.calculateShortPath(source, destination);
                printResults(source, destination);
            }

        } catch (IOException e) {
            System.err.println(e);
        } finally {
            sc.close();
        }
    }

    private void printResults(int source, int destination) {
        System.out.print("["+source+"->"+destination+"]\t");
        if (!m.hasPath()) {
            System.out.println("No Path");
            return;
        }

        System.out.printf("%.2f\n",m.distance());
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        System.out.print("输入地图文件: ");
        String map_data=sc.next();
        System.out.print("输入路径问题文件: ");
        String questions_data=sc.next();
        Distances dis = new Distances(new InputData(map_data).getGraph(), questions_data);
        sc.close();
    }


    /**
     * <p>为Distances问题优化的MyDijkstra算法
     * <p>由于Distances问题只需求得路径的最短距离而无需路径，因此可以省去相关的变量以及方法
     * 
     * @author Chen Junjie
     */
    private class MyDijkstraForDistances extends MyDijkstra{
        private double[] distTo; // distTo[v] = distance of shortest s->v path
        private double[] total_cost_to; // 储存原点到节点的总代价，为实际代价+估算代价
        private IndexMultiwayMinPQ<Double> pq; // priority queue of vertices

        private List<Integer> moddified; // 记录上次修改过的节点
        private EuclidienGraph graph;
        private int last_source; // 记录上次查询的起始节点
        private int current_destination;

        public MyDijkstraForDistances(EuclidienGraph G) {
            super(G);
            for (Edge e : G.edges()) {
                if (e.weight() < 0)
                    throw new IllegalArgumentException("edge " + e + " has negative weight");
            }

            distTo = new double[G.V()];
            total_cost_to = new double[G.V()];

            this.graph = G;
            last_source = -1; // 对象实例化时不存在上次查询的起始节点，故初始化为-1
            moddified = new ArrayList<Integer>();

            // 初始化所有节点的distTo和总代价
            for (int v = 0; v < graph.V(); v++) {
                distTo[v] = Double.POSITIVE_INFINITY;
                total_cost_to[v] = Double.POSITIVE_INFINITY;
            }
        }

        // 指定起始节点与目的节点计算最短路径
        // 通过distance与path方法获取最短距离与最短路径
        @Override
        public void calculateShortPath(int source, int destination) {
            validateVertex(source);
            validateVertex(destination);
            this.current_destination = destination;

            if (source != last_source) {
                for (int v : moddified) {
                    distTo[v] = Double.POSITIVE_INFINITY;
                    total_cost_to[v] = Double.POSITIVE_INFINITY;
                }
                moddified.clear();

                distTo[source] = 0.0;
                total_cost_to[source] = 0.0;
                moddified.add(source);
                pq = new IndexMultiwayMinPQ<Double>(graph.V(), 3);
                pq.insert(source, total_cost_to[source]);
            }

            // 如果本次查询的路径在上次的查询中已经计算出来了，则直接利用上次查询的结果。
            if (source == last_source && !pq.contains(destination) && hasPathTo(destination))
                return;

            last_source = source;
            // relax vertices in order of distance from s

            while (!pq.isEmpty()) {
                int v = pq.delMin();
                for (Edge e : graph.adj(v))
                    /**
                     * 在MyDijkstra算法中此处若没有横切边判断可能会产生路径信息错误
                     * 但距离信息不受影响，因此此处无需判断
                     */
                    relax(e, v); 
                if (v == destination)
                    break; // 检查目的节点的最短路径是否已经求出
            }

            // check optimality conditions
            assert check(graph, source);
        }

        // relax edge e and update pq if changed
        private void relax(Edge e, int v) {
            int w = e.other(v);

            // 计算新总代价
            double new_cost = total_cost_to[v] + e.weight()
                    + graph.getPoint(w).distanceTo(graph.getPoint(current_destination))
                    - graph.getPoint(v).distanceTo(graph.getPoint(current_destination));

            if (total_cost_to[w] > new_cost) {
                total_cost_to[w] = new_cost;
                distTo[w] = distTo(v) + e.weight();
                if (pq.contains(w))
                    pq.decreaseKey(w, total_cost_to[w]);
                else {
                    pq.insert(w, total_cost_to[w]);
                    moddified.add(w); // 第一次放松v-w的边，导致distTo[w]的值修改，保存修改记录
                }

            }
        }

        @Override
        public double distance() {
            return distTo(current_destination);
        }

        @Override
        public boolean hasPath() {
            return hasPathTo(current_destination);
        }

        @Override
        public double distTo(int v) {
            validateVertex(v);
            return distTo[v];
        }

        @Override
        public boolean hasPathTo(int v) {
            validateVertex(v);
            return distTo[v] < Double.POSITIVE_INFINITY;
        }


        // check optimality conditions:
        // (i) for all edges e = v-w: distTo[w] <= distTo[v] + e.weight()
        // (ii) for all edge e = v-w on the SPT: distTo[w] == distTo[v] + e.weight()
        private boolean check(EuclidienGraph G, int s) {

            // check that edge weights are non-negative
            for (Edge e : G.edges()) {
                if (e.weight() < 0) {
                    System.err.println("negative edge weight detected");
                    return false;
                }
            }

            // check that distTo[v] and edgeTo[v] are consistent
            if (distTo[s] != 0.0) {
                System.err.println("distTo[s] inconsistent");
                return false;
            }
            for (int v = 0; v < G.V(); v++) {
                if (v == s)
                    continue;
                if (distTo[v] != Double.POSITIVE_INFINITY) {
                    System.err.println("distTo[] inconsistent");
                    return false;
                }
            }

            // check that all edges e = v-w satisfy distTo[w] <= distTo[v] + e.weight()
            for (int v = 0; v < G.V(); v++) {
                for (Edge e : G.adj(v)) {
                    int w = e.other(v);
                    if (distTo[v] + e.weight() < distTo[w]) {
                        System.err.println("edge " + e + " not relaxed");
                        return false;
                    }
                }
            }

            return true;
        }

        // throw an IllegalArgumentException unless {@code 0 <= v < V}
        private void validateVertex(int v) {
            int V = distTo.length;
            if (v < 0 || v >= V)
                throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1));
        }

        public static void main(String[] args) {
            MyDijkstra m = new MyDijkstra(new InputData("data.txt").getGraph());
            m.calculateShortPath(0, 5);
            System.out.println(m.distance() + " " + m.path());
        }

    }
}
